package leetcode.dynamic;

/*

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

股票系列题解：https://leetcode-cn.com/circle/article/qiAgHn/

解法：
    1. 股票问题的dp[i][k][0], dp[i][k][1]数组的解释为：
    dp[i][k][0]表示在 i 天，k 次交易后手中没有股票的情况下的最大利润
    dp[i][k][1]表示在 i 天，k 次交易后手中持有一只股票的情况下的最大利润

    dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);// 第 i 天没有交易，依然没有持有股票，或者 第 i 天在 i- 1 持有股票的情况下交易了
    dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);// 第 i 天没有交易，依然持有股票，或者 第 i 天在 i - 1天没有股票的情况下买入了股票

    2. 最大利润的情况是第 i 天没有持股的情况即dp[i][k][0]
 */

public class LeetCode188_MaxProfit {

    public int maxProfit(int k, int[] prices) {

        if (prices.length < 2) return 0;

        int[][][] dp = new int[prices.length][k][2];
        for (int i = 0; i < k; i++){
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < prices.length; i++){
            dp[i][0][0] = max(prices, i);
            dp[i][0][1] = -prices[i];
        }

        if (k >= prices.length || k < 1) k /= 2;

        for (int i = 1; i < dp.length; i++){
            for (int j = 1; j < k; j++){
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }

        return dp[dp.length - 1][k - 1][0];

    }

    public int max(int[] prices, int day){
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i <= day; i++){
            if (prices[i] < min){
                min = prices[i];
            }
            if (prices[i] - min > max) max = prices[i] - min;
        }

        return max;
    }

    public static void main(String[] args) {

        int k = 8;
        int[] prices = {3,2,6,5,0,3};

        int i = new LeetCode188_MaxProfit().maxProfit(k, prices);

        System.out.println("i = " + i);

    }

}
